With the recent advances in network communication and electronic business transaction, it is becoming increasingly important to ensure the security of communications. One of the methods used to ensure security is cryptography. At present, communications are carried out by using a variety of cryptographic techniques.
For example, there has been put into practical use a system in which a cryptographic module is embedded in a small device such as an IC card, and data transmission/reception is performed between the IC card and a reader/writer as a data reading/writing device, thereby carrying out authentication processing, or encryption/decryption of the transmitted/received data.
IC cards executing cryptographic processing, for example, are widely used in a variety of gates such as the entrance gate of a train station or in shopping centers, and the demands for smaller size and faster processing speed are becoming increasingly stringent.
Cryptographic schemes are roughly divided into a common key scheme and a public key scheme. The common-key scheme is also referred to as symmetric cryptography. In the common key scheme, the sender and the recipient both own a common key. A typical application of the common key scheme is DES (Data Encryption Standard). The characteristic feature of a DES algorithm is that both encryption and decryption can be executed using substantially the same algorithm.
A scheme adopting a configuration in which, as opposed to the above-mentioned common key scheme, the key owned by the sender and that owned by the recipient are different is the public key scheme or asymmetric cryptography. Unlike common key cryptography in which a common key is used for encryption and decryption, public-key cryptography proves advantageous in terms of key management because only one specific person needs to own a secret key that must be kept in secret. In comparison to common key cryptography, however, public key cryptography involves lower data processing speed. As such, in general, the public key cryptography is frequently used for the distribution of secret keys, digital signatures, or other such applications involving low data volume. Typical known examples of public key cryptography includes RSA (Rivest-Shamir-Adleman) cryptography and ECC (Elliptic Curve Cryptography).
Elliptic curve cryptography uses an elliptic curve y2=x3+ax+b (where 4a3+27b2≠0) over a prime field, an elliptic curve y2+xy=x3+ax2+b (where b≠0) over two extension fields, or the like. A set including an infinity point (O) added to a point on each of these curves forms a finite group for the addition, and the infinity point O becomes the unit element thereof. In the following description, the addition of points in the finite group is represented by the operator +. The addition P+Q of two different points P, Q in the finite group is referred to as the “point addition”, and the addition P+P=2P of two points P in the finite group is referred to as the “point doubling”. An operation of adding the point P to itself k times, that is, an operation of finding a point P+P+ . . . +P=kP, is referred to as the “scalar multiplication of a point”.
As is commonly known, the scalar multiplication of a point can be computed with point addition and point doubling. The addition of points, the doubling of a point, and the scalar multiplication of a point in affine coordinates (x, y) or projective coordinates (X, Y, Z) on an elliptic curve over the prime field and an elliptic curve over two extension fields are described in IEEE P1363/D13 Standard Specifications for Public Key Cryptography.
An example of a scheme in which elliptic curve cryptography is generalized is HECC (Hyper-Elliptic Curve Cryptography) system proposed by Koblitz and Cantor. The hyperelliptic curve cryptography is described in Non-Patent Documents 1 and 2.
In elliptic curve cryptography, if P denotes a point on an elliptic curve defined over a finite field Fq, and Q denotes a point kP(kεZ), that is, a point obtained as a result of the scalar multiplication of the point P, the problem of finding k from Q can be solved as a discrete logarithmic problem. On the other hand, in hyperelliptic curve cryptography, if D, denotes be a divisor equal to a formal sum of points and D2 denotes a divisor defined as a scalar multiplication kD1, then the problem of finding k from D2 can be treated as a discrete logarithmic problem in a Jacobian variety on a hyperelliptic curve as a public key cryptography problem.
In the case of a hyperelliptic curve, a value characterizing the curve is a genus g. Let q be equal to pn (q=pn) where p denotes a prime number and n denotes a positive integer. In this case, a hyperelliptic curve C defined over the finite field Fq as a curve of the genus g is defined by the following equation:y2+h(x)y=f(x)where h(x), f(x)εFq[x], f(x) is the monic polynomial of degree 2g+1.
The opposite point −P to a point P=(x, y) on the hyperelliptic curve C is defined as −P=(x, y+h(x)). A point for which P=−P is referred to as a ramification point.
As is commonly known, assuming the same level of security as elliptic curve cryptography, the processing size (the number of bits) of a definition field of hyperelliptic curve cryptography can be reduced to 1/g times the processing size of a definition field of elliptic curve cryptography. The small processing size proves advantageous in terms of implementation, which is regarded as one of the benefits of hyperelliptic curve cryptography.
Next, the basic principles of hyperelliptic curve cryptography will be described. As described above, in hyperelliptic curve cryptography, the problem of finding k from D2 can be treated as a discrete logarithmic problem in a Jacobian variety on the hyperelliptic curve and as such can be treated as a problem in public key cryptography where D1 is a divisor equal to a formal sum of points, and D2 is a divisor defined as a scalar multiplication kD1.
In this case, a divisor is equal to a formal sum of points and can be expressed by the form:
                    D        ⁢                                  =                              ∑                          i              ⁢                                                                                                                  ⁢                                          ⁢                                    m              i                        ⁢                          P              i                                                          [                  Formula          ⁢                                          ⁢          1                ]            
Further, a semi reduced divisor can be expressed by the form:
                              D          ⁢                                          =                                                    ∑                                  i                  ⁢                                                                                                                                                      ⁢                                                          ⁢                                                m                  i                                ⁢                                  P                  i                                                      -                                          (                                                      ∑                                          i                      ⁢                                                                                                                                                                                          ⁢                                                                          ⁢                                      m                    i                                                  )                            ⁢                              P                ∞                                                    ,                              m            i                    ≥          0                                    [                  Formula          ⁢                                          ⁢          2                ]            
However, for Pi=(xi, yi) and I≠j, a relation Pi≠Pj holds true.
Σmi in the above equation is referred to as the weight of the divisor D. Further, a semi reduced divisor having a weight not exceeding the genus g is referred to as a reduced divisor.
Using the polynomials U and VεFq[x], any semi reduced devisor D in a Jacobian variety on the hyperelliptic curve can be expressed as D=(U, V). This expression is referred to as a Mumford expression. The Mumford expression is described in, for example, Non-Patent Document 3.U=Π(x−xi)mi V(xi)=yi V(x)2+V(x)h(x)−f(x)≡0 mod U(x), deg V<deg U  [Formula 3]
By using the Mumford expression, any reduced divisor D for a genus 2 can be expressed by a set of polynomials each having elements over the finite field set in the coefficients of the polynomial and having an order not exceeding 2. That is, the reduced divisor can be expressed as(U,V)=(x2+u1x+u0,v1x+v0), or(U,V)=(x+x0,y0).
Further, the zero element is expressed as(U,V)=(1,0)=O 
Next, the scalar multiplication of a divisor used in hyperelliptic curve cryptography will be described. The scalar multiplication of a divisor can be carried out as a combination of the addition of the divisor, which is referred to as an addition algorithm, and the doubling of the divisor. Major addition algorithms will be described below.
The first proposed practical algorithm is a Cantor algorithm. The Cantor algorithm is described in, for example, Non-Patent Documents 1 and 2. This Cantor algorithm is applicable to a divisor on a hyperelliptic curve of any genus. However, the drawback of this Cantor algorithm is that in comparison to an elliptic curve algorithm, the algorithm is complicated and has high complexity.
Harley proposed an algorithm in which, by limiting the algorithm to hyperelliptic curves of genus 2, a case-by-case differentiation is made depending on the weight of a divisor, and optimization is performed for each individual case to achieve a reduction in complexity. Since then, this Harley algorithm has been the subject of recent extensive studies on the improvement and extension of computation algorithms in the HECC (Hyper-Elliptic Curve Cryptography).
(a) In accordance with the Harley algorithm, the definition field is used as a prime field and the Mumford expression is adopted as an expression of a divisor on a curve with a genus 2. Examples of studies aimed at reducing the complexity of this algorithm include those disclosed in Non-Patent Document 4, Non-Patent Document 5, Non-Patent Document 6, and the like.
(b) In addition, an example of processing in which the definition field is extended with respect to two extension fields is reported in each of Non-Patent Document 7 and Non-Patent Document 8.
(c) Further, Non-Patent Documents 11, 12, 6 and 13 disclose studies according to which a reduction in complexity is accomplished by using the Mumford expression to express a divisor and adopting the weighted coordinates.
Processing using the Harley algorithm will be described with reference to FIG. 1. It should be noted that the present invention relates to a hyperelliptic curve of genus 2 defined over a finite field of a characteristic 2. In the following description, it is assumed that the genus of the curve is 2, and the characteristic of the definition field is 2.
FIG. 1A is a diagram showing a processing example of the addition of divisors, D1+D2, where D1 and D2 each denote a divisor with a genus 2. It should be noted that divisors D1 and D2 are expressed as follows: D1=(U1,V1), D2=(U2,V2). First, a case-by-case differentiation is made depending on the weight values of the divisors. That is, depending on the values of the respective weights of [D1+D2], the processing is differentiated for the following cases:
(1) weight 2+weight 2
(2) weight 2+weight 1
(3) Exceptional Processing 1
Next, in the case of addition of a weight 2 to a weight 2 itself, that is, in the case (1): weight 2+weight 2, if the greatest common denominator gcd(U1, U2) for the two divisors D1=(U1,V1) and D2=(U2,V2) is 1 (gcd(U1, U2)=1), the two divisors D1=(U1,V1) and D2=(U2,V2) do not include a common point or points opposite to each other. In this case, addition processing according to
(1a) HarleyADD,
that is, the Harley algorithm is carried out. The processing of (1a) HarleyADD is processing referred to as Most Frequent Case disclosed in, for example, Non-Patent Document 7. The Most Frequent Case is a case occurring with a high probability in the addition processing to find the sum of D1+D2 of divisors for a genus 2.
The processing of (1a) HarleyADD occurs with a very high probability. The probability with which some other exceptional processing occurs is very low. If the conditions of the most frequent case are not satisfied, that is, if the greatest common denominator gcd(U1, U2) for the two divisors D1=(U1,V1) and D2=(U2,V2)=1 is not satisfied,
(1b) Exceptional Processing 2 is carried out.
Also for the case (2) of weight 2+weight 1, in the same way, it is checked as to whether or not gcd(U1, U2)=1. If gcd(U1, U2)=1 is satisfied,ExHarADD2+1→2  (2a)is carried out, and if gcd(U1, U2)=1 is not satisfied,
(2b) Exceptional Processing 3 (2b) is carried out.
Exceptional processing 1 in the case (3) is carried out for cases of weight setting other than those of the cases (1) and (2) mentioned above.
It should be noted that the algorithm of the addition processing for a genus 2 described above is disclosed in detail in Non-Patent Document 8 (Table 1, 2).
The flow of doubling operation for a genus 2 is shown in FIG. 1(B). The doubling operation is processing represented as D+D=2D. Let D1=(U1,V1) be the input, and D2=[2]D1 be the output.
As in the case of addition, different kinds of processing are carried out depending on the weight of the devisor D, as follows:
(4): weight 2
(5): weight 1
(6): weight 0
In the case (4) of weight 2, it is checked as to whether or not the divisor includes a ramification point. If no ramification point is included, the processing of (4a) HarleyDBL is carried out. If the divisor includes a ramification point, (4b) Exceptional Processing 6 is carried out. The algorithm of the HarleyDBL processing is disclosed as being the most frequent case in, for example, Non-Patent Document 7. The algorithm of the HarleyDBL processing is shown below.
                                          Algorithm            ⁢                                                  ⁢            1            ⁢                                                  ⁢            HarleyDBL                    ⁢                                          ⁢                                    Input              ⁢                              :                            ⁢                                                          ⁢                              D                1                                      =                          (                                                U                  1                                ,                                  V                  1                                            )                                ⁢                                          ⁢                                    Output              ⁢                              :                            ⁢                                                          ⁢                              D                2                                      =                          (                                                U                  2                                ,                                  V                  2                                            )                                      ⁢                                  ⁢                                                            U                i                            ⁡                              (                x                )                                      =                                          x                2                            +                                                u                                      i                    ⁢                                                                                  ⁢                    1                                                  ⁢                x                            +                              u                                  i                  ⁢                                                                          ⁢                  0                                                              ,                                                    V                i                            ⁡                              (                x                )                                      =                                                            v                                      i                    ⁢                                                                                  ⁢                    1                                                  ⁢                x                            +                              v                                  i                  ⁢                                                                          ⁢                  0                                                              ,                                    gcd              ⁡                              (                                  h                  ,                                      U                    1                                                  )                                      =            1                          ⁢                                  ⁢                              1.            ⁢                                                  ⁢                          U              1              ′                                ←                      U            1            2                          ⁢                                  ⁢                                            2.              ⁢                                                          ⁢              S                        ←                                                            h                                      -                    1                                                  ⁡                                  (                                      f                    +                                          h                      ⁢                                                                                          ⁢                                              V                        1                                                              +                                          V                      1                      2                                                        )                                            /                              U                1                                              ,                      mod            ⁢                                                  ⁢                          U              1                                      ⁢                                  ⁢                              3.            ⁢                                                  ⁢                          V              1              ′                                ←                                    SU              1                        +                          V              1                                      ⁢                                  ⁢                              4.            ⁢                                                  ⁢                          U              2              ′                                ←                                          ⁢                                    (                              f                +                                  h                  ⁢                                                                          ⁢                                      V                    1                    ′                                                  +                                                      V                    ′                                    1                  2                                            )                        /                          U              ′                                      ⁢                                  ⁢                              5.            ⁢                                                  ⁢                          U              2                                ←                      MakeMonic            ⁡                          (                              U                2                ′                            )                                      ⁢                                  ⁢                              6.            ⁢                                                  ⁢                          V              2                                ←                                    V              1              ′                        +                          h              ⁢                                                          ⁢              mod              ⁢                                                          ⁢                              U                2                                                    ⁢                                  ⁢                              7.            ⁢                                                  ⁢            return            ⁢                                                  ⁢                          D              2                                =                      (                                          U                2                            ,                              V                2                                      )                                              [                  Formula          ⁢                                          ⁢          4                ]            
As will be described later, this processing occurs with a very high probability. The probability of the occurrence of some other exceptional processing is very low. As described above, if the conditions of the most frequent case are not satisfied, Exceptional Processing 6 is carried out.
In the case of weight 1 as well, it is checked whether or not gcd(U1, U2)=1, and the processing of (5a), ExHarDBL1+1→2, or Exceptional Processing 7 as the processing (5b) is carried out. The algorithm of ExHarDBL1+1→2 is disclosed in Non-Patent Document 8[4.12. (a)].
As described above, HarleyADD and HarleyDBL are referred to as the most frequent case. If a divisor is generated at random and is subjected to addition or doubling, the processing of HarleyADD or HarleyDBL occurs with a very high probability. It should be noted that description about HarleyADD and HarleyDBL becoming the most frequent case is given in, for example, Non-Patent Document 14.
In accordance with Non-Patent Document 14, the probability of the occurrence of processing other than the above-mentioned most frequent case is O(1/q) where q denotes the number of elements in the definition field. Since qg is a large number with a required size of about 160 in secure cryptographic applications, in practice, it can be regarded that only HarleyADD or HarleyDBL occurs.
Thus, when the addition algorithm of HECC (Hyper-Elliptic Curve Cryptography) is implemented as cryptographic computation means such as an IC card by using the Harley algorithm or an improved algorithm thereof, it is often the case that only
HarleyADD, and
HarleyDBL
are implemented, and other types of complicated exceptional processing that has almost zero probability of occurrence are not executed. Examples of the method applied to exceptional processing in this case include execution of a Cantor algorithm that does not require case-by-case differentiation depending on the weight value. Since the larger the genus, the greater the load of the complicated exceptional processing, this implementation method is specially described in Non-Patent Documents 9 and 10.
Next, scalar multiplication of a divisor in the algorithm of HECC (Hyper-Elliptic Curve Cryptography) will be described. In the algorithm of the HECC (Hyper-Elliptic Curve Cryptography), scalar multiplication of a divisor is carried out as a combination of hyperelliptic addition and hyperelliptic doubling. The algorithm of the scalar multiplication will be described by taking the basic binary method and basic double-and-add-always method as examples.
As described above, in elliptic curve cryptography, assuming that P denotes a point on an elliptic curve defined over a finite field Fq, Q denotes a point kP(kεZ), that is, a point obtained as a result of the scalar multiplication of the point P, the problem of finding k from Q can be solved as a discrete logarithmic problem. On the other hand, in hyperelliptic curve cryptography, assuming that D1 denotes a divisor equal to a formal sum of points and D2 denotes a divisor defined as a scalar multiplication kD1, the problem of finding k from D2 can be treated as a discrete logarithmic problem in a Jacobian variety on the hyperelliptic curve as a public key cryptography problem.
In this case, the binary expression of a scalar value: d as a multiplier to be applied to a scalar multiplication (D=dD) is given as follows:d=(d1-1, . . . , d0)
wherein d1-1=1, and d1-2, . . . , 0=1 or 0.
As the algorithm for scalar multiplication, the computation algorithms of the basic binary method include the following:
binary (left-to-right) method; and
binary (right-to-left) method.
According to the binary (right-to-left) method, d is scanned from the least significant bits, and if di=1, [2i]D is added. The algorithm (Algorithm 2) of the binary (right-to-left) method is shown below.
                              Algorithm          ⁢                                          ⁢          2          ⁢                                          ⁢          binary          ⁢                                          ⁢                      (                          right              ⁢                              -                            ⁢              to              ⁢                              -                            ⁢              left                        )                    ⁢                                          ⁢          method                ⁢                                  ⁢                  Input          ⁢                                          ⁢                      D            0                          ⁢                                  ⁢                              Output            ⁢                                                  ⁢            D                    =                      d            ⁢                                                  ⁢                          D              0                                      ⁢                                  ⁢                  T          ←                      D            0                          ⁢                                  ⁢                  D          ←          O                ⁢                                  ⁢                              for            ⁢                                                                      ⁢                                                                    ⁢                          i              ⁢              from                        ⁢                                                  ⁢            0            ⁢                                                  ⁢            to            ⁢                                                  ⁢            l                    -          1                ⁢                                  ⁢                  {                                          ⁢                                          ⁢                                    if              ⁢                                                          ⁢                              d                i                                      =                                                            1                  ⁢                                                                          ⁢                  then                  ⁢                                                                          ⁢                  D                                ←                                  D                  +                  T                                            //                                                Addition                  ⁢                                                                          ⁢                  HarleyADD                  ⁢                                                                          ⁢                                                                          ⁢                  T                                ←                                  2                  ⁢                                                                          ⁢                  T                  ⁢                                      //                                    ⁢                  Doubling                  ⁢                                                                          ⁢                  HarleyDBL                                                              ⁢                                          }                ⁢                                  ⁢                  return          ⁢                                          ⁢          D                                    [                  Formula          ⁢                                          ⁢          5                ]            
On the other hand, according to the binary (left-to-right) method, d is scanned from the most significant bits, D is doubled for every bit, and if di=1, a base point is added. The algorithm (Algorithm 3) of the binary (left-to-right) method is shown below.
                              Algorithm          ⁢                                          ⁢          3          ⁢                                          ⁢          binary          ⁢                                          ⁢                      (                          left              ⁢                              -                            ⁢              to              ⁢                              -                            ⁢              right                        )                    ⁢                                          ⁢          method                ⁢                                  ⁢                  Input          ⁢                                          ⁢                      D            0                          ⁢                                  ⁢                              Output            ⁢                                                  ⁢            D                    =                      d            ⁢                                                  ⁢                          D              0                                      ⁢                                  ⁢                  D          ←                      D            0                          ⁢                                  ⁢                              for            ⁢                                                                      ⁢                                                                    ⁢            i            ⁢                                                  ⁢            from            ⁢                                                  ⁢            l                    -                      2            ⁢                                                  ⁢            downto            ⁢                                                  ⁢            0                          ⁢                                  ⁢                  {                                          ⁢                                          ⁢                                    D              ←                                                [                  2                  ]                                ⁢                D                ⁢                                  //                                ⁢                Doubling                ⁢                                                                  ⁢                HarleyDBL                ⁢                                                                  ⁢                                                                  ⁢                if                ⁢                                                                  ⁢                                  d                  i                                                      =                                                  ⁢                                          1                ⁢                                                                  ⁢                then                ⁢                                                                  ⁢                D                            ←                              D                +                                                      D                    0                                    ⁢                                      //                                    ⁢                  Addition                  ⁢                                                                          ⁢                  HarleyADD                                                              ⁢                                          }                ⁢                                  ⁢                  return          ⁢                                          ⁢          D                                    [                  Formula          ⁢                                          ⁢          6                ]            
Next, base-point generation processing will be described. When applying scalar multiplication to cryptography, divisors D0 necessary for the inputs are divided into the following two types:
(1): a divisor determined in advance; and
(2): a divisor undeterminable in advance and generated at random.
In the case of type (1) of a divisor determined in advance, the input divisor is referred to as a base point.
A general algorithm for generating a base point is described as follows.
(a): g elements on a definition field Fq are selected at random and g points Pi (where i=1, . . . , g) on a hyperelliptic curve are generated.                (a1): The elements selected at random are each used as an x coordinate xi (where i=1 . . . g). Then, a y coordinate corresponding to xi is determined so that every point (x, y) is positioned on the hyperelliptic curve.        
(b): Let D0=(U(x), V(x)) represent the divisor of the base point.                (b1): U(x)=(x−x1)(x−x2) . . . (x−xg)        (b2): Coefficients vi of an equation V(x)=vg-1xg−1+vg-2xg−2+ . . . +v0 are determined. If the generated points are all different from each other, for example, the coefficients vi can be found from an equation V(xi)=yi. (c): The divisors generated in accordance with the above algorithm are each a divisor with a weight of g.        
If the computation of scalar multiplication is applied to cryptography, a divisor D0 required for the input, that is, a base point is generated. If divisors determined in advance are applied to the generation of a base point, it is possible to find a divisor with a weight of g as a divisor usable as a base point by carrying out the processing (a) to (c) described above.
Further, with regard to elliptic curve cryptography, halving of a rational point has been proposed. For example, halving of a rational point in elliptic curve cryptography is disclosed in Non-patent Document 15, Patent Document 1, and Patent Document 2. In the disclosed processing, when computing the scalar multiplication of a rational point, instead of using addition and doubling, addition and halving are used.
Halving in elliptic curve cryptography can be computed generally faster than doubling. As a result, scalar multiplications using halving can be computed fast. Non-patent Document 16 reports that in the case of a software implementation with the [Intel PentiumIII 800 MHz] from Intel Corporation as a processor, with respect to a definition field Fq, q=2163, halving is approximately 2.1 times faster than doubling, and with respect to a definition field Fq, q=2233, halving is approximately 2.6 times faster than doubling. Since hyperelliptic curve cryptography represents the generalization of elliptic curve cryptography, there may be cases where the operations used in elliptic curve cryptography can be extended to hyperelliptic curve cryptography. For example, Non-patent Documents 17 and 18 disclose a case where the Montgomery method, which realizes fast computation since a y-coordinate is not used for computation in elliptic curve cryptography, is extended to hyperelliptic curve cryptography. It is anticipated that if halving faster than doubling can be realized also in hyperelliptic curve cryptography, the scalar multiplication of a divisor, too, can be computed faster than in the related art. However, the use of such halving operation is not known in the related art. It should be noted that Non-patent Document 19 is an example of a published document presenting a fast computation technique using doublings.    [Patent Document 1] E. Knudsen. COMPUTING METHOD FOR ELLIPTIC CURVE CRYPTOGRAPHY, WO 01/04742 A1, 18 Jan. 2001    [Patent Document 2] R. Schroeppel. Elliptic curve point ambiguity resolution apparatus and method, WO 01/35573 A1, 17 May 2000    [Non-patent Document 1] N. Koblitz. Hyperelliptic curve cryptosystems. J. Cryptology, vol. 1, No. 3, pp. 139-150, 1989.    [Non-patent Document 2] D. G. Cantor. Computing in the Jacobian of hyperelliptic curve. Math. Comp., Vol. 48, No. 177, pp. 95-101, 1987    [Non-patent Document 3] “D. Mumford, Tata lectures on theta II, Progress in Mathematics, no. 43, Birkhauser, 1984.”    [Non-patent Document 4] K. Matsuo, J. Chao, and S. Tsujii. Fast Genus two hyperelliptic curve cryptosystems. Technical Report ISEC2001-31, IEICE Japan, 2001.    [Non-patent Document 5] M. Takahashi. Improving Harley algorithms for Jacobians of genus 2 hyperelliptic curves. SCIS2002. (Japanese).    [Non-patent Document 6] T. Lange. Inversion operation-free arithmetic on genus 2 hyperelliptic curves. Cryptology ePrint Archive, 2002/147, IACR, 2002.    [Non-patent Document 7] T. Sugizaki, K. Matsuo, J. Chao, and S. Tsujii. An extension of Harley addition algorithm for hyperelliptic curves over finite fields of characteristic two. ISEC2002-9, IEICE, 2001    [Non-patent Document 8] T. Lange, Efficient arithmetic on genus 2 hyperelliptic curves over finite fields via explicit formulae. Cryptology ePrint Archive, 2002/121, IACR, 2002.    [Non-patent Document 9] J. Kuroki, M. Gonda, K. Masuo, J. Chao and S. Tsujii. Fast genus three hyperelliptic curve cryptosystems. SCIS2002    [Non-patent Document 10] J. Pelzl, T. Wollinger, J. Guajardo, and C. Paar. Hyperelliptic curve Cryptosystems: Closing the Performance Gap to Elliptic Curves. Cryptology ePrint Archive, 2003/026, IACR, 2003.    [Non-patent Document 11] Y. Miyamoto, H. Doi, K. Matsuo, J. Chao and S. Tsujii. A fast addition algorithm of genus two hyperelliptic curves. SCIS2002. (Japanese).    [Non-patent Document 12] N. Takahashi, H. Morimoto and A. Miyaji. Efficient exponentiation on genus two hyperelliptic curves (II). ISEC2002-145, IEICE, 2003. (Japanese)    [Non-patent Document 13] T. Lange. Weighed coordinate on genus 2 hyperelliptic curve. Cryptology ePrint Archive, 2002/153, IACR, 2002.    [Non-patent Document 14] N. Nagao. Improving group law algorithms for Jacobians of hyperelliptic curves. ANTS-IV, LNCS 1838, pp. 439-448, Springer-Verlag, 2000.    [Non-patent Document 15] E. Knudsen. Elliptic Scalar Multiplication Using Point Halving. ASIACRYPTO '99, LNCS 1716, pp. 135-149, Springer-Verlag, 1999.    [Non-patent Document 16] K. Fong, D. Hankerson, J. Lopez, and A. Menezes. Field inversion operation and point halving revised. Technical Report CORR2003-18, www.cacr.math.uwaterloo.ca/techreports/2003/corr2003-18.pdf    [Non-patent Document 17] S. Dquesne. Montgomery Scalar Multiplication for Genus 2 Curves. ANTS-VI, LNCS 3076, pp. 153-168, 2004.    [Non-patent Document 18] T. Lange. Montgomery Addition for Genus Two Curves. ANTS-VI, LNCS 3076, pp. 309-317, 2004.    [Non-patent Document 19] T. Lange. Efficient Doubling on Genus Two Curves over Binary Fields, SAC 2004, pre-proceedings, pp. 189-202, 2004.